문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 피보나치 수열 (문단 편집) == 유래 == 피사의 레오나르도로 널리 알려진 [[레오나르도 피보나치]]가 1202년 [[토끼]]의 번식을 언급하면서 이 수에 대하여 연구했다. 하지만, 피보나치가 최초로 연구한 것은 아니고 [[인도]]의 수학자가 최초란 기록이 남아있다. 기원전 450년 핑갈라가 쓴 책에서 최초로 이 패턴이 언급되었고 이후 인도의 수학자들이 이 수에 대하여 연구한 흔적들이 발견되었다. 그 때문에 피보나치도 동방쪽에서 넘어온 정보를 접한 적이 있지 않았을까 생각하는 무리들도 있긴 하나 공식적인 연관성은 불명. 어쨌든 [[서유럽]]에서 이 수열을 연구하고 체계화할 수 있는 업적을 세운 것은 피보나치였기 때문에 피보나치 수열이란 이름이 붙게 됐다. 다만 피보나치수열이란 이름은 19세기가 되어서야 붙여졌다. 실제 피보나치수열의 점화식은 인도도 그렇고 유럽도 그렇고 일찌감치 알려져 있었으나 피보나치 수의 생성함수는 완전히 정리되기까지 다소 시간이 필요했다. [[1765년]] [[레온하르트 오일러|오일러]]가 최초로 이 생성함수를 정리하여 발표했으나 당시에는 별로 주목을 받지 못해서 그대로 묻혔다. 이후 [[1848년]] 비네가 이 생성함수를 재발견하여 발표했고 결국 피보나치 수의 생성함수는 비네의 식이라 이름이 붙었다. 물론 오일러는 다른 방면에서도 어마어마하게 유명하므로 아쉬울 일은 없을 것이다. 수학의 수열 파트에서 잠시 배우는 수준이지만 컴퓨터 계열로 진학할 경우 정말 질리도록 보게 된다. [[프로그래밍 언어]]에서 [[재귀함수]]를 배우면서 과제로 반드시 한 번은 하게 된다. 재귀함수로 간단히 구현되지만, [[메모이제이션]](Memoization) 없이 구현할 경우 실행시간이 안드로메다로 증가하게 된다. 반대로 메모이제이션을 할 경우에는 필요한 메모리가 O(n) 에 비례해지는 단점이 있다. 단순히 직전과 그 전의 값만 저장하는 방식으로 반복문이나 꼬리재귀 최적화가 된 재귀를 할 경우 시간복잡도 O(n)에 공간복잡도 O(1)도 가능하다. 다만, 정말 큰 임의의 n에 대한 피보나치 수를 구해야한다면, 행렬을 이용하여 시간복잡도 O(log n)에 공간복잡도 O(1)로 구현할 수도 있다. 좀더 높은 레벨의 프로그래밍에서는 피보나치 힙(Fibonacci Heap) 같이 자료구조나 알고리즘 최적화에 피보나치 수열의 성질을 우려먹는 경우를 많이 보게 될 것이다. 자연에서 꽃씨의 배열이나 나무가지의 갈라짐 등등으로 빈번하게 등장하고, 피보나치의 문제처럼 실제 생물의 번식을 설명하는 데에도 쓰인다. 이는 [[황금비]]의 자기닮음성이나 [[프랙탈]]과도 엮인다.[* 다만 이것이 와전되어 [[황금비]]를 유사과학적으로 접근하는 사람들이 생겨났다.] 비슷한 맥락으로 주식시장의 변동을 설명하는 엘리어트 파동 이론(Elliott wave theory)에서 출현하기도 한다. 여러 모로 신기한 수열이다. 베리에이션으로 뤼카 수열(Lucas Sequence)이 있다. 초항과 그 다음 항을 0과 1이 아닌 숫자 두 개를 설정하고 [math( F_{ n + 2 } = F_{ n } + F_{ n + 1 } )]대로 따라가면 뤼카 수열이다. [[수학 귀신]]에도 꽤나 나온다. 번식하는 토끼의 수를 나타내거나 아래에 나오는 두 항의 비율이 황금비에 근접하는 사실 등.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기